
/**
 * @Project : Clion_ProgrammingExercises
 * @File : 2482
 * @Author : WangRuoyu 
 * @Date : 2023/9/6 16:03
 */

#include "iostream"
#include "vector"
#include "algorithm"
#include "unordered_map"

using namespace std;

const int MOD = 1e9 + 7;

bool cmp(int a, int b) {
    return a > b;
}

long long cmn(int m, int n) {
    if (m - n < n) return cmn(m, m - n);
    long long res = 1;
    for (int i = 1; i <= n; ++i) {
        res *= m - i + 1;
        res /= i;
        res %= MOD;
    }
    return res;
}

class Solution {
public:
    int countKSubsequencesWithMaxBeauty(string s, int k) {
        if (k > 26) return 0;
        long long res = 1;
        int f[26] = {0};
        unordered_map<int, int> map;

        for (int i = 0; i < s.size(); ++i) {
            f[s[i] - 'a']++;
        }

        sort(f, f + 26, cmp);
        int snum = 0;
        for (int i = 0; i < 26; ++i) {
            map[f[i]]++;
            if (f[i] > 0) snum++;
        }

        if (snum < k) return 0;

        for (int i = 0; i < 26;) {
            int cnt = map[f[i]];
            if (k >= cnt) {
                for (int j = 0; j < cnt; ++j) {
                    res = res * f[i] % MOD;
                }
                i += cnt ;
                k -= cnt;
                if (k == 0) break;
            } else {
                for (int j = 0; j < k; ++j) {
                    res = res * f[i] % MOD;
                }
                res = res * cmn(cnt, k) % MOD;;
                k = 0;
                break;
            }
        }

        return (int) res;

    }
};

int main() {
    Solution sl;
    string s = "dpdemprzvz";
    int k = 1;
    cout << sl.countKSubsequencesWithMaxBeauty(s, k);
    return 0;
}